package com.mystudy.leetcode.problem.tree.p_563;

/**
 * @program: infoalgorithm
 * @description: 二叉树的坡度
 * @author: zhouzhilong
 * @create: 2019-08-09 15:24
 **/

import com.mystudy.leetcode.base.TreeNode;
import com.mystudy.leetcode.base.TreeNodeUtils;
import org.junit.After;
import org.junit.Before;
import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * 给定一个二叉树，计算整个树的坡度。
 * <p>
 * 一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
 * <p>
 * 整个树的坡度就是其所有节点的坡度之和。
 * <p>
 * 示例:
 * <p>
 * 输入:
 * 1
 * /   \
 * 2     3
 * 输出: 1
 * 解释:
 * 结点的坡度 2 : 0
 * 结点的坡度 3 : 0
 * 结点的坡度 1 : |2-3| = 1
 * 树的坡度 : 0 + 0 + 1 = 1
 * 注意:
 * <p>
 * 任何子树的结点的和不会超过32位整数的范围。
 * 坡度的值不会超过32位整数的范围。
 */
public class Solution {
    private static final Logger LOGGER = LoggerFactory.getLogger(Solution.class);

    long startTime = 0L;
    long endTime = 0L;


    @Before
    public void before() {
        startTime = System.nanoTime();
    }

    @Test
    public void test() {
        TreeNode root = TreeNodeUtils.generateTwoTrees(new Integer[]{1, 2, 3});
        int tilt = findTilt(root);
        LOGGER.debug("tilt = [{}]", tilt);

    }

    @After
    public void after() {
        endTime = System.nanoTime();
        double cost = (endTime - startTime) / 1000000.0;
        LOGGER.debug("cost = [{} ms ]", cost);
    }

    int tilt = 0;

    public int findTilt(TreeNode root) {
        if (root == null) {
            return 0;
        }
        getSum(root);
        return tilt;
    }

    private int getSum(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftSum = getSum(node.left);
        int rightSum = getSum(node.right);
        int curTilt = Math.abs(leftSum - rightSum);
        tilt += curTilt;
        return leftSum+rightSum+node.val;
    }
}
